Data communication networks may include various computers, servers, nodes, routers, switches, bridges, hubs, proxies, and other network devices coupled to and configured to pass data to one another. These devices will be referred to herein as “network elements.” Data is communicated through the data communication network by passing protocol data units over communication links interconnecting the network elements. The data may be organized into discrete pieces for transmission on the communication network, so that multiple data streams may share the resources of the communication network. Common ways of segmenting data include creation of Internet Protocol (IP) packets or Ethernet frames which may be individually forwarded across the communication network. A particular protocol data unit may be handled by multiple network elements and cross multiple communication links as it travels between its source and its destination over the network.
The various network elements on the communication network communicate with each other using predefined sets of rules, referred to herein as protocols. Different protocols are used to govern different aspects of the communication, such as how signals should be formed for transmission between network elements, various aspects of what the protocol data units should look like, how protocol data units should be handled or routed through the network by the network elements, and how the network elements should exchange information between each other to enable them to interoperate on the network.
Ethernet is a well known networking protocol that has been defined by the Institute of Electrical and Electronics Engineers (IEEE) as standard 802.3, which specifies the physical layer, and 802.1, which specifies the network layer. This application is focused on the network layer aspect and, as used herein, the term “Ethernet network” refers to a network which implements one or more of the 802.1 family of protocols including, for example, 802.1, 802.1Q, 802.1ad, 802.1ah, 802.1Qay, or 802.1aq. The 802.1 family of protocols generally specifies that an Ethernet header be applied to a packet so that nodes on the network may forward the packet toward its intended destination. Depending on the particular protocol in use on the network, this Ethernet header may include a source MAC address, destination MAC address, one or more Virtual Local Area Network Identifiers (VIDs) and optionally other fields. Multiple headers may be included as well, for example a first header may be applied using a client MAC addressing space and a second outer header may be included using network service provider MAC addressing space.
In Ethernet network architectures, devices connected to the network compete for the ability to use shared telecommunications paths at any given time. Where multiple bridges or nodes are used to interconnect network segments, multiple potential paths to the same destination often exist. A benefit of this architecture is that it provides path redundancy between bridges and permits capacity to be added to the network in the form of additional links. However to prevent loops from being formed, a spanning tree was generally used to restrict the manner in which traffic was broadcast or flooded on the network. A characteristic of spanning tree is that there is only one path between any pair of destinations in the network, and therefore it was possible to “learn” the connectivity associated with a given spanning tree by watching where packets came from. 802.1Q, 802.1ad, and 802.1ah all use one or more spanning tree instances in the control plane to determine which links should be active and which should be blocked to prevent the formation of loops.
To overcome some of the limitations inherent in Ethernet networks implementing a spanning tree, IEEE 802.1aq has been developed which enables the nodes on the network to implement a link state routing protocol to control forwarding of Ethernet frames on the network. Two examples of link state routing protocols include Open Shortest Path First (OSPF) and Intermediate System to Intermediate System (IS-IS). As used herein, the term “link state protocol controlled Ethernet network” will refer to an 802.1 Ethernet network, which uses a link state routing protocol to control installation of forwarding state which is used by the nodes to forward data traffic on the network.
When a link state protocol is used to control the Ethernet network, rather than utilizing a learned network view at each node by using the Spanning Tree Protocol (STP) algorithm combined with transparent bridging, the bridges forming the network exchange link state advertisements to enable each node to have a synchronized view of the network topology. This is achieved via the well understood mechanism of a link state routing system. The bridges in the network have a synchronized view of the network topology, have knowledge of the requisite unicast and multicast connectivity, can compute a shortest path connectivity between any pair of bridges in the network, and individually can populate their forwarding information bases (FIBs) according to the computed view of the network.
When all nodes have computed their role in the synchronized view and populated their FIBs, the network will have a loop-free unicast tree to any given bridge from the set of peer bridges (those that require communication to that bridge for whatever reason); and a both congruent and loop-free point-to-multipoint (p2mp) multicast tree from any given bridge to the same set or subset of peer bridges per service instance hosted at the bridge. The result is the path between a given bridge pair is not constrained to using the links on the spanning tree and the overall result can better utilize the breadth of connectivity of a set of nodes interconnected in a mesh. In essence every bridge roots one or more trees which define unicast connectivity to that bridge, and multicast connectivity from that bridge.
In Ethernet networks, like other networks, handling of failures is important to ensure continued availability of the network. Typically networks aim to have the network recover from a failure within 50 msec. Also, from an implementation standpoint, ideally it is desirable to implement failure recovery without requiring additional tunnels to be signaled on the network and without requiring additional encapsulation. For example, in an MPLS network, fast re-route has been developed which allows traffic to be placed on an alternate path through the network upon occurrence of a failure. However, the fast reroute solution needs signaling, requires the nodes on the MPLS network to maintain state for the tunnels, and needs encapsulation for even two hop reroute tunnels. Further, MPLS reroute is not applicable to Ethernet since it requires IP addressing, which is not native to Ethernet. Accordingly, it would be desirable to provide a method and apparatus for implementing distributed failure recovery in a routed Ethernet network.